\section{Related work}
\label{sec:related}

In this section, we review related work that is most relevant to our
research. We have classified previous related work into areas of
interests (epidemiology, social networks, economics, and network
security). We also give a brief overview of some of the mathematical
and computational techniques and models that have been developed in
previous work.

\smallskip
\BfPara{Epidemiology} The study of spread of diseases and the ways to
control them has been a major research topic for centuries. One of the
earliest documented scientific studies of vaccination policy was due
to Bernoulli, who analyzed smallpox morbidity and mortality data to
demonstrate the effectiveness of vaccination
\cite{blower:bernoulli}. He presented a mathematical model for
calculating the cost and benefits of smallpox vaccination, and
presented a convincing mathematical analysis for universal
vaccination. Modern epidemiological analysis is largely based on an
elegant class of models, called SIR
(susceptible-infected-recovered). This model was first formulated by
Reed and Frost in 1920s, and has been developed over the decades. In
the SIR model, the population is divided into three groups:
susceptible (S), infected (I), and recovered (R), as shown in Figure
\ref{fig:sir}. A {\em susceptible} individual becomes {\em infected}
at a certain rate, $\beta$, when contacting with other infected
individuals. Once infected, an individual may either recover and
receive lifelong immunity or die at a certain rate, $\nu$. In either
case, it moves to {\em recovered} group. The lifelong immunity
assumption is suitable for most common childhood diseases (measles,
mumps, rubella, etc.). Another well studied model is the SIS
(susceptible-infected-susceptible) model, shown in Figure
\ref{fig:sis}. In SIS model, when an individual recovers from an
infection, it moves back to the susceptible group
\cite{weiss+d:SIS}. Because recovered individuals can be infected
again, this model is good to model fast mutated diseases, like
seasonal flu.

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=3.5in]{figures/sir.jpg}
    \caption{SIR model.}
    \label{fig:sir}
  \end{center}
\end{figure}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=2.5in]{figures/sis.jpg}
    \caption{SIS model.}
    \label{fig:sis}
  \end{center}
\end{figure}

The SIR model and its variants have been highly influential in the
study of epidemics
\cite{yang+h1n109,manski+partial10,medlock+optvacc09,kaplan+smallpox02,grassly+model08,blower+imperfect93}. These
models, however, do not attempt to capture the rich and structure of
the contact network, along which interactions occur. Network structure
has a direct effect on both the spread of diseases as well as the
nature of interactions, which has been observed by a number of
researchers, e.g. \cite{Ne03, jackson10}. In the emerging area of
contact network epidemiology, an underlying contact graph captures the
patterns of interactions which leads to the transmission of a disease
\cite{lloyd+m:epidemiology,meyers06,meyers+sars05,newman:spread02}. Many
studies have predicted the spread of diseases through networks using
mathematical analysis or simulations, e.g. estimating the size of an
epidemic, or determining the basic reproductive rate (see
\cite{meyers06} for some pointers).

Over the past decade, a number of researchers have analyzed the
effectiveness of control strategies in a game-theoretic setting
\cite{bauch+game03,bauch+game04,bauch:dynamic05,cojocaru08}. Such
studies enable the comparison between Nash equilibria strategies
driven by self-interest \cite{AspnesCY2006,galvani+rc:influenza07} and
those centralized strategies proposed by health agencies.

A major focus of the thesis is on how intervention strategies may in
turn cause risky behavior and affect network dynamics, which
significantly affect the equilibrium and resulting perverse social
outcomes. The counterintuitive impact of vaccination owing to risky
behavior was first discovered by Blower and McLean
\cite{blower+risk94,blower:chapter} in the case of HIV. Subsequently,
several independent studies have confirmed this phenomenon and have
offered potential explanations
\cite{smith+b:hiv04,bezemer08,wilson+cwb,velasco}. However, no formal
models have been proposed for studying the interplay between
interventions, network dynamics, and individual behaviors.


\smallskip
\BfPara{Computer viruses and networking} Several researchers have
analyzed network security problems and the spread of viruses in
computer networks
\cite{AspnesCY2006,berger+episcalefree05,ganesh05,grossklags,lelarge+b:security,wang03}. Another
direction of work is based on SIS models for the worm spread, e.g. the
$n$-intertwined model \cite{orda:infocom09}. In this model, nodes are
in two states: susceptible or infected. Each infected node spreads the
infection to its neighbors with some probability.

Non-cooperative game theory has been used in analyzing a number of
problems in traffic and communication networks, e.g. routing
\cite{roughgarden}, topology control and network formation
\cite{eidenbenz06,nahir:infocom09}, and security
\cite{grossklags,orda:infocom09}. The basic question of interest have
usually been about the existence, the structure of Nash equilibria,
and the price of anarchy, which is the worst case cost of Nash
equilibrium to the social optimum \cite{koutsoupias99worst}. See
\cite{nisan:book} for a good introduction on the use of game theoretic
techniques for networking applications.

\smallskip
\BfPara{Social networks and economics} The spread of contagion,
influence, or behavior, in social networks has been extensively
studied.  This has spawned the research area of {\em network games},
starting from the seminal work of Jackson and
Wolinsky~\cite{jackson+wolinsky:strategic}, and Bala and
Goyal~\cite{BalaGoyal} on how networks are formed when individuals
choose to add or sever links so as to maximize their influence.  A
variety of game-theoretic models have been developed to study diverse
applications including the very formation of
networks~\cite{jackson+wolinsky:strategic,BalaGoyal,johari-contractbased,fabrikant03network},
provision of public goods~\cite{bramoulle+k:networks}, and research
collaboration among firms~\cite{goyal+m:RandD}.
(See~\cite{jackson:book,goyal:book,galeotti+gjvy:network} for
excellent overviews of this research area.)  Most relevant to this
project is prior work on the diffusion of social and economic behavior
in networks, e.g., purchase of a product or adoption of a
technology~\cite{galeotti:consumer}, decision to undertake criminal
activity~\cite{ballester+cz:network}.  While much of prior research
has assumed that perfect information is available to all players, more
recent work has developed models for incomplete
information~\cite{galeotti+gjvy:network,jackson+y:diffusion}.  There
are several fundamental differences between our proposed project and
this line of previous research.  First, the focus of our work is on
the {\em impact of intervention strategies on the spread of
  contagion}, rather than analyzing how contagions spread.  Second, we
take into account {\em changes in the network} in the course of the
diffusion process.  Third, we consider a much {\em richer strategy
  space}\/ which takes into account temporal issues (when an
intervention is adopted) and the strength of the interventions; in
contrast, previous work assumes binary strategy spaces.

There is a huge body of work on {\em gossiping}, applied to both the
spread of ideas in a social network as well as routing or broadcast of
data in a communication
network~\cite{karp+ssv:rumor,feige+pru:broadcast,pittel:rumor,boyd+gps:gossip}.
Several analyses have been given for gossip-based routing
protocols~\cite{braginsky+e:rumor,elsasser+s:broadcast,kempe+k:gossip}.
Gossiping has also proved effective in aggregate computations in
distributed networks~\cite{kempe+dg:gossip,deb+mc:gossip}.  Recent
work has considered gossiping in dynamic adversarial
networks~\cite{avin+kl:dynamic,kuhn+lo:dynamic}.  Combinatorial
optimization aspects of influence spread are explored in
\cite{KempeKT03,KempeKT05} where the goal is to pick an initial set in
a stochastic model with maximal expected influence. This model is
extended further in \cite{BharathiKS07} to a competitive setting
within the stochastic framework where different players compete
(sequentially) to maximize their expected influence.


\smallskip
\BfPara{Models and techniques} The SIR, SIS, and related models in
epidemiology can be characterized in terms of differential equations,
which captures the rate of change of the susceptible, infected, and
recovered individuals.

Contact network epidemiology enhance these models with contact
graphs. Contact graphs are also important aspects of models in network
security and social networks. A number of random graph models have
been considered for modeling contacts
(e.g. \cite{meyers+sars05,gardenes+biscalefree07,meloni+episcalefree09}). The
most basic random graph model is due to Erd\"{o}s and R\'{e}nyi
\cite{erdos1960} and Gilbert \cite{gilbert59}, who defined the
$G(n,m)$ and $G(n,p)$ models. In the former, a graph is chosen
uniformly at random from all $n$-vertex $m$-edge graphs, while the
latter is an $n$-vertex graph in which each edge appears independently
at random with probability $p$. A number of alternative random graph
models have been suggested in an attempt to yield random graphs with
more general type of degree distribution. Molloy and Reed's model is
based on considering random graphs of fixed order with a given
arbitrary degree distribution
\cite{molloy+arbitrarydegree95,molloy+arbitrarydegree98,newman+arbitrarydegree01}. Later,
Chung and Lu proposed a model to generate random graphs with expected
degree distribution \cite{chung+ccsize02,chung+distance03}. Other
models motivated by specific real-world networks include Kleinberg's
small world random graphs
\cite{kleinberg+nature00,kleinberg+smallworld00}, and
Barab\'{a}si-Albert preferential attachment graph
\cite{barabasi:science99}. The preferential attachment model is a
mechanism for generating random scale-free graphs
\cite{barabasi:science99,bollobas+degreeseq01}, which have been
observed to capture important properties of several real world
networks, including the Internet AS-level graph
\cite{faloutsos+powerlaw99}, the Worldwide Web
\cite{barabasi+web99,kleinberg+webgraph99}, human sexual contact
network \cite{liljeros+sexnet01}, scientific collaborations network
\cite{barabasi+collaboration02}.

The spread of diseases/viruses in networks has been analyzed by a
variety of methods: model-based simulations
\cite{albert+errorattack00,pastor+episcalefree,cornforth+rsbgm:flu};
percolation theory techniques using differential equations and
generating functions that yield asymptotic analysis
\cite{soderberg+inhomo02,newman:spread02,wormald:differential};
rigorous probabilistic techniques that apply to finite random graph
models
\cite{bollobas+inhomo,bollobas+errorattack04,berger+episcalefree05};
and game-theoretic analysis that studies uniqueness, complexity, and
the structure of equilibria
\cite{chen+dk:vaccinate,nisan:book,jackson+y:diffusion,galeotti+gjvy:network}.
